package com.sortingalgorithm;

import java.util.Arrays;

// 堆排序（大顶堆）
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {1,3,6,7,2,54,54,4};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static void heapSort(int [] arr){
        // 建堆
        heapInsert(arr);
        int size = arr.length;
        while (size > 1){
            // 把最大值放到最后一位
            swap(arr,0,size - 1);
            size--;
            // 剩下的调整大顶堆
            heapVerify(arr,0,size);
        }
    }


    // 构造大顶堆（大根堆）
    private static void heapInsert(int [] arr){
        int len = arr.length;
        for(int i = 0;i < len;i++){
            // 得到当前结点的索引
            int currentIdx = i;
            // 计算当前结点的父节点的索引
            int fatherIdx =( (currentIdx - 1) >> 1);
            //如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点
            //然后继续和上面的父结点值比较，直到不大于父结点，则退出循环
            while (fatherIdx > -1 &&arr[currentIdx] > arr[fatherIdx]){
                // 交换当前结点和父节点的值
                swap(arr,currentIdx,fatherIdx);
                // 当前索引指向父索引
                currentIdx = fatherIdx;
                fatherIdx = (currentIdx - 1) >> 1;
            }
        }
    }

    // 调整堆
    private static void heapVerify(int [] arr,int index,int size){
        int left = 2 * index + 1 ;
        int right = 2 * index + 2;
        while (left < size){
            int largeIdx;
            // 判断孩子节点中较大值的索引（这里必须保证有右结点的存在）
            if(arr[left] < arr[right] && right < size){
                largeIdx = right;
            }else{
                largeIdx = left;
            }
            // 确定后找父节点和孩结点的较大值
            if(arr[index] > arr[largeIdx]){
                largeIdx = index;
            }
            // 如果父节点的索引值和最大值相同 说明是大根堆
            if(largeIdx == index){
                break;
            }
            // 否则交换
            swap(arr,largeIdx,index);
            // 将索引指向孩子中较大的值的索引
            index = largeIdx;
            //重新计算交换之后的孩子的索引
            left = 2 * index + 1;
            right = 2 * index + 2;
        }

    }

    // 交换
    private static void swap(int[] arr,int i ,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    
}
